
var res [][]string

func partition(s string) [][]string {
    res = make([][]string, 0)
    backTracking(s, 0, []string{})
    return res
}

func backTracking(s string, startIndex int, sliceArr []string){
    if startIndex == len(s) { // 切割到字符串尾部了
        tem := make([]string, len(sliceArr))
        copy(tem, sliceArr)
        res = append(res, tem)
        return 
    }
    for i:=startIndex; i<len(s); i++ {
        if isPalindrome(s, startIndex, i) {
            sliceArr = append(sliceArr, s[startIndex:i+1])
        } else {
            continue
        }
        backTracking(s, i+1, sliceArr)
        sliceArr = sliceArr[:len(sliceArr)-1]
    }

}

func isPalindrome(s string, start int, end int) bool {
    left := start
    right := end
    for left<right {
        if s[left] != s[right] {
            return false
        }
        left ++
        right --
    }
    return true
}


var res [][]string
var path []string
// 暴力回溯法 22_5_22
func partition(s string) [][]string {
    /*
        力扣 131
        1. 递归函数参数

        2. 递归中止条件
                    aab
            切割a 切割aa 切割aab
        从ab中切割 ...    ...

        3. 单层递归逻辑
    */
    res = make([][]string, 0)
    path = make([]string, 0)
    backTracking(s, 0, path, &res)
    return res
}

func backTracking(s string, startIndex int, path []string, res *[][]string) {
    // fmt.Println(path)
    // 中止条件
    if startIndex >= len(s) {
        deepCopyPath := make([]string, len(path))
        copy(deepCopyPath, path)
        *res = append(*res, deepCopyPath)
        return
    }
    // 主循环
    for i:=startIndex; i<len(s); i++ {
        if subS, ok := isHuiWen(s, startIndex, i); ok {
            path = append(path, subS)
            backTracking(s, i+1, path, res)
            path = path[:len(path)-1]
        }
    }
}

func isHuiWen(s string, start int, end int) (string, bool) {
    for i, j := start, end; i<=j ; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return "", false
        }
    }
    return s[start:end+1], true
}

